#include<cstdio>
#include<iostream>
#include<stack>
#include<queue>
#include<map>
using namespace std;
struct Huffnode
{
    int weight;
    unsigned char data;
    Huffnode *left,*right,*pa;
};
bool is_come[1000][1000];
bool comp(Huffnode *a,Huffnode *b)
{
    return a->weight > b->weight;
}
Huffnode *createHuffmanTree(int Gray[])
{
    priority_queue<Huffnode*,vector<Huffnode*>,decltype(&comp)>q(&comp);
    for(int k=0;k<256;k++)
    {
        if(Gray[k]>0)
        {
            Huffnode *temp = new Huffnode;
            temp->weight=Gray[k];
            temp->data=k;
            temp->left=temp->right=temp->pa=NULL;
            q.push(temp);
        }
    }
    while(q.size()>1)
    {
        Huffnode *le=q.top();
        q.pop();
        Huffnode *ri=q.top();
        q.pop();
        Huffnode *root=new Huffnode;
        root->weight=le->weight+ri->weight;
        root->data=0;
        root->left=le;
        root->right=ri;
        root->pa=NULL;
        le->pa=ri->pa=root;
        q.push(root);
    }
    return q.top();
}
map <unsigned char,unsigned char> createHuffmancode(Huffnode *root)
{
    map <unsigned char,unsigned char>code;
    stack<Huffnode*>s;
    s.push(root);
    while(!s.empty())
    {
        Huffnode *temp=s.top();
    }
}
void Huffman_zip(unsigned char *buf,int m,int n)
{
    int Gray[256];
    memset(Gray,0,sizeof(Gray));
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            Gray[buf[i*n+j]]++;
        }
    }
    Huffnode *root=createHuffmanTree(Gray);
    map<unsigned char,unsigned char>code;
    code=createHuffmancode(root);
}
void regionGrowing_raw(unsigned char *buf, int m, int n, int seed_y, int seed_x, int thresh, unsigned char *bufOut)
{
	stack<pair<int ,int>>s;
	int dx[8]={-1,0,1,-1,1,-1,0,1};
	int dy[8]= {-1,-1,-1,0,0,1,1,1};
	s.push(make_pair(seed_x,seed_y));
	memset(is_come,0,sizeof(is_come));
	is_come[seed_y][seed_x]=true;
	while(!s.empty())
	{
		int x=s.top().first;
		int y=s.top().second;
		s.pop();
		unsigned char temp=buf[y*n+x];
		for(int k=0;k<8;k++)
		{
			int nextx=x+dx[k];
			int nexty=y+dy[k];
			if(nextx<0||nextx>=n||nexty<0||nexty>=m)continue;
			if(is_come[nexty][nextx])continue;
			if(fabs((int)temp-(int)buf[nexty*n+nextx])<=thresh)
			{
				bufOut[nexty*n+nextx]=0;
				s.push(make_pair(nextx,nexty));
				is_come[nexty][nextx]=true;
			}
			else{
				bufOut[nexty*n+nextx]=255;
				s.push(make_pair(nextx,nexty));
				is_come[nexty][nextx]=true;
			}
		}

	}
}

int main()
{
	int m, n, seedx, seedy, thresh;
	FILE *fp;
	fp=fopen("/Users/yuzhengze/Documents/C++/数据结构/Huffman_XU/目标图像/1.raw", "rb");//路径要修改成自己电脑的路径
	m=300, n=400, seedy=150, seedx=200, thresh=22;

	unsigned char *buf = new unsigned char[m * n];
	fread(buf, sizeof(unsigned char), m*n, fp);
	fclose(fp);
	
	unsigned char *bufOut = new unsigned char[m * n];
    Huffman_zip(buf,m,n);
	regionGrowing_raw(buf, m, n, seedy, seedx,  thresh, bufOut);//
	fp=fopen("/Users/yuzhengze/Documents/C++/数据结构/Huffman_XU/目标图像/1_out.raw","wb");//新建输出文件要跟读入文件不重名
	fwrite(bufOut, sizeof(unsigned char), m * n, fp);
	fclose(fp);
	delete []buf;
	delete []bufOut;

}